package FrequentSequenceMining;

import java.util.ArrayList;
import java.util.HashMap;

public class SequenceList {
	public static final double MINFREQUENCY = 0.001;
	private ArrayList<ArrayList<Sequence>> sequences; 
	private static SequenceList instance;
	
	public SequenceList() {
		sequences = new ArrayList<ArrayList<Sequence>>();
	}
	
	public static SequenceList getInstance() {
		if(instance == null) {
			instance = new SequenceList();
		}
		return instance;
	}
	
	public void setLengthOneSequences(ArrayList<Sequence> lengthOneSequences) {
		sequences.add(lengthOneSequences);
	}
	
	public boolean generateNewSequences() {
		int n = sequences.size();
		ArrayList<Sequence> previousSequences = sequences.get(n-1);
		ArrayList<Sequence> newSequences = new ArrayList<Sequence>();
		//generate sequences of length n+1 and delete the nonfrequent ones
		
		int m = previousSequences.size();
		for (int i=0; i<m; i++){
			Sequence seq1 = previousSequences.get(i);
			int firstIndex = 0;
			String secondWord = null;
			if(seq1.getSequence().size() > 1) { 
				secondWord = seq1.getSequence().get(1);
				firstIndex = firstIndexOf(secondWord, previousSequences);
			}
			for (int j=firstIndex; j<m; j++) {
				if(i!=j){
					Sequence seq2 = previousSequences.get(j); 
					if(canMerge(seq1, seq2)) {
						Sequence merged = merge(seq1,seq2);
						if(merged.getFrequency()>=MINFREQUENCY){
							newSequences.add(merged);							
							System.out.println(merged);
						}
					}
					else if(seq1.getSequence().size() > 1 && secondWordNoMatch(secondWord, seq2)) {
						break;
					}
				}
			}
		}
		if(newSequences.size() == 0) return false;
		sequences.add(newSequences);
		return true;
	}

	
	private boolean secondWordNoMatch(String secondWord, Sequence seq2) {
		return seq2.getSequence().get(0).equals(secondWord);
	}

	//returns position of first occurrence of word in the first position of a sequence 
	private int firstIndexOf(String word, ArrayList<Sequence> sequences) {
		//return 0;
		System.out.println("Searching for: " + word);
		int result = binarySearchRec(word, sequences, 0, sequences.size()-1);
		if(result == -1) return sequences.size(); //not found, no sequences to search
		return result;
	}

	private int binarySearchRec(String word, ArrayList<Sequence> sequences, int start, int end) {
		if(start >= end) {
			if(sequences.get(start).getSequence().get(0).equals(word)) return end;
			else return -1;
		}
		int mid = (start+end)/2;
		
		String toCompare = sequences.get(mid).getSequence().get(0);
		//System.out.println("Comparing from " + start + "  to " + end + ", element " + mid +", word: " +toCompare);
		if(toCompare.compareTo(word) > 0) { 
			return binarySearchRec(word, sequences, mid+1, end);
		}
		else { //if(toCompare.compareTo(word) < 0) {
			return binarySearchRec(word, sequences, start, mid);
		}
		//return mid;
	}

	private boolean canMerge(Sequence s1, Sequence s2){
		ArrayList<String> seq1 = s1.getSequence();
		if(seq1.size() == 1) return true;
		ArrayList<String> seq2 = s2.getSequence();
		return seq1.subList(1, seq1.size()).equals(seq2.subList(0, seq1.size()-1));
	}
	
	private Sequence merge(Sequence s1, Sequence s2) {
		return s1.mergeWith(s2);
	}

	public ArrayList<ArrayList<Sequence>> getAllSequences() {
		return sequences;		
	}
	
}
